﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Sort
{
    class RadixSort
    {
        static void Main()
        {
            Console.WriteLine("RadixSort.");
            int[] arr = { 10, 12, 23, 31, 52, 0, 98, 87, 79, 66, 45 };
            Random rd = new Random();
            for (int j = 0; j < 1000; j++)
            {
                for (int i = 0; i < 10; i++)
                {
                    arr[i] = rd.Next(100);
                }
                Sort(arr);
                if (!Utils.CheckOrderArray(arr))
                {
                    Console.WriteLine("error.");
                }
                //Utils.WriteArr(arr);
            }
        }

        public static void Sort(int[] arr)
        {
            SortByDigit(arr, 1);
            SortByDigit(arr, 2);
        }

        static void SortByDigit(int[] arr, int d)
        {
            int radix = 10;
            int[] count = new int[radix];
            int[] bucket = new int[arr.Length];

            // 置空各个桶的数据统计
            for (int i = 0; i < radix; i++)
            {
                count[i] = 0;
            }

            // 统计各个桶将要装入的数据个数
            for (int i = 0; i < arr.Length; i++)
            {
                int j = GetDigit(arr[i], d);
                count[j]++;
            }

            // count[i]表示第i个桶的右边界索引
            for (int i = 1; i < radix; i++)
            {
                count[i] = count[i] + count[i - 1];
            }

            // 将数据依次装入桶中
            for (int i = arr.Length-1; i >= 0; i--)
            {
                int j = GetDigit(arr[i], d);
                bucket[count[j] - 1] = arr[i];
                count[j]--;
            }
            
            // 将已分配好的桶中数据再倒出来，此时已是对应当前位数有序的表
            Buffer.BlockCopy(bucket, 0, arr, 0, arr.Length*sizeof(int));
        }

        static int GetDigit(int x, int d)
        {
            int[] a = {
                    1, 1, 10, 100
            }; // 本实例中的最大数是百位数，所以只要到100就可以了
            return ((x / a[d]) % 10);
        }

        static void radixSort(int[] list, int begin, int end, int digit)
        {
            int radix = 10; // 基数
            int i = 0, j = 0;
            int[] count = new int[radix]; // 存放各个桶的数据统计个数
            int[] bucket = new int[end - begin + 1];
 
            // 按照从低位到高位的顺序执行排序过程
            for (int d = 1; d <= digit; d++) {
 
                // 置空各个桶的数据统计
                for (i = 0; i < radix; i++) {
                    count[i] = 0;
                }
 
                // 统计各个桶将要装入的数据个数
                for (i = begin; i <= end; i++) {
                    j = GetDigit(list[i], d);
                    count[j]++;
                }
 
                // count[i]表示第i个桶的右边界索引
                for (i = 1; i < radix; i++) {
                    count[i] = count[i] + count[i - 1];
                }
 
                // 将数据依次装入桶中
                // 这里要从右向左扫描，保证排序稳定性
                for (i = end; i >= begin; i--) {
                    j = GetDigit(list[i], d); // 求出关键码的第k位的数字， 例如：576的第3位是5
                    bucket[count[j] - 1] = list[i]; // 放入对应的桶中，count[j]-1是第j个桶的右边界索引
                    count[j]--; // 对应桶的装入数据索引减一
                }
 
                // 将已分配好的桶中数据再倒出来，此时已是对应当前位数有序的表
                for (i = begin, j = 0; i <= end; i++, j++) {
                    list[i] = bucket[j];
                }
            }
        }
    }
}
